package com.str.graphs;
public class ListGraph implements Graph { // Graph: Adjacency list

  private class Edge {
  	int vertex;
  	int weight;
  	Edge next;
  	
  	Edge(int v, int w, Edge n) {
  	  vertex = v;
  	  weight = w;
  	  next = n;
    }
  }

  private Edge[] list;   // The vertex list
  private int numVertex; // Number of vertices
  private int numEdge;   // Number of edges

  public ListGraph(int num) { // Constructor
  	list = new Edge[num];
  	numVertex = num;
  	numEdge = 0;                 
  }

  public int n() { return numVertex; } // Number of vertices

  public int e() { return numEdge; }   // Number of edges

  public int first(int v) { // Get the first edge for a vertex
    Edge curr = list[v];
    if (curr == null) return numVertex;
    else return curr.vertex;
  }

  public int next(int v1, int v2) { // Get next edge for a vertex
    Edge curr = list[v1];
    if (curr == null) return numVertex;
    else {
      while ((curr != null) && (curr.vertex < v2))
        curr = curr.next;
      if ((curr != null) && (curr.vertex == v2) && (curr.next != null))
        return curr.next.vertex;
      else return numVertex;                // Return n if none
    }
  }

  public void setEdge(int v1, int v2, int wgt) { // Set edge weight
    if (wgt <= 0) {
      System.out.println("Illegal weight value");
      return;
    }
    Edge curr = list[v1];
    if ((curr == null) || (curr.vertex > v2)) {
      list[v1] = new Edge(v2, wgt, curr);
      numEdge++;
    }
    else if (curr.vertex == v2)
      curr.weight = wgt;
    else {
      while ((curr.next != null) && (curr.next.vertex < v2))
        curr = curr.next;
      if ((curr.next != null) && (curr.next.vertex == v2))
        curr.next.weight = wgt;
      else {
        curr.next = new Edge(v2, wgt, curr.next);
        numEdge++;
      }
    }
  }

  public int weight(int v1, int v2) { // Return weight of (v1, v2)
    for (Edge curr = list[v1]; curr != null; curr = curr.next)
      if (curr.vertex == v2) return curr.weight;
    return 0;  // No such edge
  }
} // class Graphl
